home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / modula.arc / BINGCD.MOD < prev    next >
Encoding:
Text File  |  1985-05-30  |  1.0 KB  |  48 lines
  1. (* Compute the greatest common divisor (gcd) of two natuaral
  2.    numbers.  Use addition, subtraction, doubling and halving only. *)
  3.  
  4. MODULE binarygcd;
  5. FROM InOut IMPORT ReadInt, WriteInt, WriteLn, WriteString;
  6.  
  7. VAR a,b: INTEGER;
  8.  
  9. PROCEDURE gcd(x,y: INTEGER): INTEGER;
  10. VAR u,v,d, a,b,k: INTEGER;
  11. BEGIN
  12.   u := x; v := y;
  13.   a := 0; b := 0;
  14.   WHILE NOT ODD(u) DO
  15.     u := u DIV 2;
  16.     INC(a);
  17.   END;
  18.   WHILE NOT ODD(v) DO
  19.     v := v DIV 2;
  20.     INC(b);
  21.   END;
  22.   IF a < b THEN k := a ELSE k := b END;
  23.   d := u-v;
  24.   WHILE d # 0 DO
  25.     REPEAT d := d DIV 2 UNTIL ODD(d);
  26.     IF d < 0 THEN v := -d ELSE u := d END;
  27.     d := u-v;
  28.   END;
  29.   WHILE k > 0 DO
  30.     u := 2*u;
  31.     k := k-1;
  32.   END;
  33.   RETURN u
  34. END gcd;
  35.  
  36. BEGIN
  37.   WriteString('Enter a> ');
  38.   ReadInt(a); WriteLn;
  39.   WHILE a # 0 DO
  40.     WriteString('Enter b> ');
  41.     ReadInt(b); WriteLn;
  42.     WriteInt(a,6); WriteInt(b,6);
  43.     WriteInt(gcd(a,b),6); WriteLn;
  44.     WriteString('Enter a> ');
  45.     ReadInt(a); WriteLn
  46.   END
  47. END binarygcd.
  48.